package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;

/**
 * TODO 用回溯/DFS重写一下
 * https://leetcode.com/problems/restore-ip-addresses/discuss/30944/Very-simple-DFS-solution
 * https://leetcode.com/problems/restore-ip-addresses/
 *
 * @author tzp
 * @since 2020/9/11
 */
public class LC93 implements Backtracking {
    public static void main(String[] args) {
        System.out.println(new LC93().restoreIpAddresses("123411189"));
        System.out.println(new LC93().restoreIpAddresses("101023"));
        System.out.println(new LC93().restoreIpAddresses("0000"));
        // 1 1 1 1 1
        // 255 255 111 135
    }

    public List<String> restoreIpAddresses(String s) {
        final String c = ".";
        final String z = "0";
        HashSet<String> result = new HashSet<>();
        int l = s.length();
        if (l < 4 || l > 12) {
            return Collections.emptyList();
        }

        for (int s1 = 1; s1 <= 3; s1++) {
            String ip1s = s.substring(0, s1);
            if (s1 > 1 && ip1s.startsWith(z)) {
                continue;
            }
            int ip1 = Integer.parseInt(ip1s);
            if (ip1 > 255) {
                break;
            }
            for (int s2 = 1; s2 <= 3; s2++) {
                if (s1 + s2 >= l) {
                    break;
                }

                String ip2s = s.substring(s1, s1 + s2);
                if (s2 > 1 && ip2s.startsWith(z)) {
                    continue;
                }
                int ip2 = Integer.parseInt(ip2s);
                if (ip2 > 255) {
                    break;
                }

                for (int s3 = 1; s3 <= 3; s3++) {
                    if (s1 + s2 + s3 >= l) {
                        break;
                    }
                    String ip3s = s.substring(s1 + s2, s1 + s2 + s3);
                    if (s3 > 1 && ip3s.startsWith(z)) {
                        continue;
                    }
                    int ip3 = Integer.parseInt(ip3s);
                    if (ip3 > 255) {
                        break;
                    }
                    String ip4s = s.substring(s1 + s2 + s3);
                    if (l - s1 - s2 - s3 > 1 && ip4s.startsWith(z)) {
                        continue;
                    }
                    int ip4 = Integer.parseInt(ip4s);
                    if (ip4 > 255) {
                        continue;
                    }

                    result.add(ip1 + c + ip2 + c + ip3 + c + ip4);
                }
            }
        }
        return new ArrayList<>(result);
    }
}
